﻿using DataProcess.Mathematics;
using System;
using System.Collections.Generic;

namespace DataProcess.Sort
{

    /// <summary>
    /// 基数排序
    /// </summary>
    public class RedixSort
    {
        private DetailDouble[] rexitems;
        private int maxLength, maxac;

        private DetailDouble[] ToRedix(double[] arr, NumberType type)
        {
            List<DetailDouble> items = new List<DetailDouble>();
            for (int i = 0; i < arr.Length; i++)
            {
                DetailDouble interger = new DetailDouble(arr[i]);

                if (type == interger.Type)
                {
                    items.Add(interger);
                }
            }

            return items.ToArray();
        }

        private void ResetPackages(List<double>[] packages)
        {
            for (int i = 0; i < packages.Length; i++)
            {
                packages[i].Clear();
            }
        }

        private void PutToPackages(List<double>[] packages, int pos, NumberPosition position)
        {
            for (int i = 0; i < rexitems.Length; i++)
            {
                DetailDouble redix = rexitems[i];

                if (position == NumberPosition.小数点后)
                {
                    redix.IsReverse = !redix.IsReverse;
                }
                int index = redix[position, pos];

                packages[index].Add(rexitems[i].OrginNumber);
            }
        }

        private int MaxLength()
        {
            int l = 0;
            foreach (DetailDouble redix in rexitems)
            {
                if (redix.Length > l)
                {
                    l = redix.Length;
                }
            }
            return l;
        }

        private int MaxAC()
        {
            int l = 0;
            foreach (DetailDouble redix in rexitems)
            {
                if (redix.Accuracy > l)
                {
                    l = redix.Accuracy;
                }
            }
            return l;
        }

        private void SortOnce(List<double>[] packages, NumberType type)
        {
            List<double> tmp = new List<double>();
            for (int i = 0; i < packages.Length; i++)
            {
                for (int j = 0; j < packages[i].Count; j++)
                {
                    tmp.Add(packages[i][j]);

                }

            }
            rexitems = ToRedix(tmp.ToArray(), type);
            Expand();
        }

        private void Expand()
        {
            for (int i = 0; i < rexitems.Length; i++)
            {
                rexitems[i].ExpandLength(maxLength);
                rexitems[i].Accuracy = maxac;
            }
        }

        private double[] BasicSort(double[] arr, NumberType type, NumberPosition position = NumberPosition.小数点前)
        {
            rexitems = ToRedix(arr, type);
            if (rexitems.Length == 0)
            {
                return new double[0];
            }

            maxLength = MaxLength();
            maxac = MaxAC();
            Expand();
            List<double>[] packages = new List<double>[10];
            for (int i = 0; i < packages.Length; i++)
            {
                packages[i] = new List<double>();
            }
            int loop;
            if (position == NumberPosition.小数点前)
            {
                loop = maxLength;
            }
            else
            {
                loop = maxac;
            }

            for (int i = 0; i < loop; i++)
            {
                PutToPackages(packages, i, position);
                SortOnce(packages, type);
                ResetPackages(packages);
            }
            List<double> result = new List<double>();
            foreach (DetailDouble item in rexitems)
            {
                result.Add(item.OrginNumber);
            }
            return result.ToArray();
        }

        private void SortCheck(double[] arr, NumberType type)
        {

            List<double> t = new List<double>();
            int start = -1;
            int? last = null;
            for (int i = 0; i < arr.Length; i++)
            {
                int now = (int)arr[i];
                if (last != null)
                {
                    if (start < 0)
                    {
                        if (last == now)
                        {
                            start = i - 1;
                            t.Add(arr[start]);
                            t.Add(arr[i]);
                        }
                    }
                    else
                    {
                        if (last == now)
                        {
                            t.Add(arr[i]);
                        }
                        else
                        {
                            double[] tmp = BasicSort(t.ToArray(), type, NumberPosition.小数点后);
                            int i1 = 0;
                            for (int j = start; j < i; j++)
                            {
                                arr[j] = tmp[i1++];
                            }
                            t.Clear();
                            start = -1;
                        }
                    }
                }
                last = now;

            }
            if (t.Count > 0)
            {
                double[] tmp = BasicSort(t.ToArray(), type, NumberPosition.小数点后);
                int i1 = 0;
                for (int j = start; j < arr.Length; j++)
                {
                    arr[j] = tmp[i1++];
                }
            }
        }


        /// <summary>
        /// 整数的判断
        /// </summary>
        /// <param name="arr"></param>
        public void Sort(double[] arr)
        {

            double[] f = BasicSort(arr, NumberType.负数);
            SortCheck(f, NumberType.负数);
            double[] z = BasicSort(arr, NumberType.正数);
            SortCheck(z, NumberType.正数);
            int j = 0;
            for (int i = f.Length - 1; i >= 0; i--)
            {
                arr[j++] = f[i];
            }

            for (int i = 0; i < z.Length; i++)
            {
                arr[j++] = z[i];
            }
        }


    }


    /// <summary>
    /// 数据排序，去重
    /// </summary>
    public class DataTool
    {
        /// <summary>
        /// 打乱数组
        /// </summary>
        /// <typeparam name="T">数组类型</typeparam>
        /// <param name="datas">需要被打乱的数组</param>
        public void MixAll<T>(T[] datas)
        {
            Random random = new Random();
            for (int i = 0; i < datas.Length; i++)
            {
                int a = random.Next(0, datas.Length);
                int b = random.Next(0, datas.Length);
                Swap(datas, a, b);
            }
        }

        private void Swap<T>(T[] alldatas, int a, int b)
        {
            T tmp = alldatas[a];
            alldatas[a] = alldatas[b];
            alldatas[b] = tmp;
        }
        /// <summary>
        /// 快速排序条件判定接口
        /// </summary>
        public interface ISortCondition
        {
            /// <summary>
            /// before大于等于key时返回true
            /// </summary>
            /// <param name="before">作为排序依据的对象</param>
            /// <param name="key">另一个作为排序依据的对象（排序的坐标值）</param>
            /// <returns></returns>
            bool SortConditionBefore(object before, object key);
            /// <summary>
            /// after小于等于key时返回true
            /// </summary>
            /// <param name="after">作为排序依据的对象</param>
            /// <param name="key">另一个作为排序依据的对象（排序的坐标值）</param>
            /// <returns></returns>
            bool SortConditionAfter(object after, object key);
        }
        private int sortUnit<T>(T[] array, ISortCondition sort, int low, int high)
        {
            T key = array[low];
            while (low < high)
            {
                /*从后向前搜索比key小的值*/
                while (sort.SortConditionBefore(array[high], key) == true && high > low)
                {
                    --high;
                }
                /*比key小的放左边*/
                array[low] = array[high];
                /*从前向后搜索比key大的值，比key大的放右边*/
                while (sort.SortConditionAfter(array[low], key) == true && high > low)
                {
                    ++low;
                }
                /*比key大的放右边*/
                array[high] = array[low];
            }
            /*左边都比key小，右边都比key大。//将key放在游标当前位置。//此时low等于high */
            array[low] = key;
            return high;
        }
        /// <summary>
        /// 自定义类型数组的排序
        /// </summary>
        /// <typeparam name="T">需要排序的对象类型</typeparam>
        /// <param name="array">需要排序的数组</param>
        /// <param name="sort">排序的判定函数</param>
        /// <param name="low">数组的起始位置，一般为0</param>
        /// <param name="high">数组的最后位置，一般为数组长度-1</param>
        public void CustomQuickSort<T>(T[] array, ISortCondition sort, int low, int high)
        {
            if (low >= high)
            {
                return;
            }
            /*完成一次单元排序*/
            int index = sortUnit(array, sort, low, high);
            /*对左边单元进行排序*/
            CustomQuickSort(array, sort, low, index - 1);
            /*对右边单元进行排序*/
            CustomQuickSort(array, sort, index + 1, high);
        }
        private int sortUnit(int[] array, int low, int high)
        {
            int key = array[low];
            while (low < high)
            {
                /*从后向前搜索比key小的值*/
                while (array[high] >= key && high > low)
                {
                    high--;
                }
                /*比key小的放左边*/
                array[low] = array[high];
                /*从前向后搜索比key大的值，比key大的放右边*/
                while (array[low] <= key && high > low)
                {
                    low++;
                }
                /*比key大的放右边*/
                array[high] = array[low];
            }
            /*左边都比key小，右边都比key大。//将key放在游标当前位置。//此时low等于high */
            array[low] = key;
            return high;
        }
        private int sortUnit(double[] array, int low, int high)
        {
            double key = array[low];
            while (low < high)
            {
                /*从后向前搜索比key小的值*/
                while (array[high] >= key && high > low)
                {
                    high--;
                }
                /*比key小的放左边*/
                array[low] = array[high];
                /*从前向后搜索比key大的值，比key大的放右边*/
                while (array[low] <= key && high > low)
                {
                    low++;
                }
                /*比key大的放右边*/
                array[high] = array[low];
            }
            /*左边都比key小，右边都比key大。//将key放在游标当前位置。//此时low等于high */
            array[low] = key;
            return high;
        }
        private void QuickSort(int[] array, int low, int high)
        {
            if (low >= high)
            {
                return;
            }
            /*完成一次单元排序*/
            int index = sortUnit(array, low, high);
            /*对左边单元进行排序*/
            QuickSort(array, low, index - 1);
            /*对右边单元进行排序*/
            QuickSort(array, index + 1, high);
        }
        private void QuickSort(double[] array, int low, int high)
        {
            if (low >= high)
            {
                return;
            }
            /*完成一次单元排序*/
            int index = sortUnit(array, low, high);
            /*对左边单元进行排序*/
            QuickSort(array, low, index - 1);
            /*对右边单元进行排序*/
            QuickSort(array, index + 1, high);
        }
        /// <summary>
        /// 快速排序（适合数据量庞大的）
        /// </summary>
        /// <param name="array">需要排序的数组</param>
        /// <param name="low">数组的起始位置，一般为0</param>
        /// <param name="high">数组的最后位置，一般为数组长度-1</param>
        public void QuickCollate(int[] array, int low, int high)
        {
            QuickSort(array, low, high);
        }
        /// <summary>
        /// 快速排序（适合数据量庞大的）
        /// </summary>
        /// <param name="array">需要排序的数组</param>
        /// <param name="low">数组的起始位置，一般为0</param>
        /// <param name="high">数组的最后位置，一般为数组长度-1</param>
        public void QuickCollate(double[] array, int low, int high)
        {
            QuickSort(array, low, high);
        }
        /// <summary>
        /// 排序
        /// </summary>
        /// <param name="num">需要排序的数组</param>
        /// <param name="isBigToSmall">true:从大到小排序，false：以小到大排序</param>
        /// <returns></returns>
        public int[] SelectCollate(int[] num, bool isBigToSmall = true)
        {
            int[] res = new int[num.Length];
            int i, j, k;
            for (i = 0; i < num.Length - 1; i++)
            {
                k = i;
                for (j = i + 1; j < num.Length; j++)
                {
                    if (num[k] > num[j])
                    {
                        k = j;
                    }
                }
                if (k != i)
                {
                    Swap(num, k, i);
                }
            }
            switch (isBigToSmall)
            {
                case true:
                    for (i = 0; i < num.Length; i++)
                    {
                        res[i] = num[num.Length - 1 - i];
                    }
                    break;
                case false:
                    for (i = 0; i < num.Length; i++)
                    {
                        res[i] = num[i];
                    }
                    break;
            }
            return res;
        }

        /// <summary>
        /// 排序
        /// </summary>
        /// <param name="num">需要排序的数组</param>
        /// <param name="isBigToSmall">true:从大到小排序，false：以小到大排序</param>
        /// <returns></returns>
        public double[] SelectCollate(double[] num, bool isBigToSmall = true)
        {
            double[] res = new double[num.Length];
            int i, j, k;
            for (i = 0; i < num.Length - 1; i++)
            {
                k = i;
                for (j = i + 1; j < num.Length; j++)
                {
                    if (num[i] > num[j])
                    {
                        k = j;
                    }
                }
                if (k != i)
                {
                    Swap(num, k, i);
                }
            }
            switch (isBigToSmall)
            {
                case true:
                    for (i = 0; i < num.Length; i++)
                    {
                        res[i] = num[num.Length - 1 - i];
                    }
                    break;
                case false:
                    for (i = 0; i < num.Length; i++)
                    {
                        res[i] = num[i];
                    }
                    break;
            }
            return res;
        }
        /// <summary>
        /// 排序
        /// </summary>
        /// <param name="num">需要排序的数组</param>
        /// <param name="isBigToSmall">true:从大到小排序，false：以小到大排序</param>
        /// <returns></returns>
        public int[] BobCollate(int[] num, bool isBigToSmall = true)
        {
            int[] res = new int[num.Length];
            int i, j;
            for (i = 0; i < num.Length - 1; i++)
            {
                for (j = 0; j < num.Length - 1 - i; j++)
                {
                    if (num[j] > num[j + 1])
                    {
                        Swap(num, j, j + 1);
                    }
                }
            }
            switch (isBigToSmall)
            {
                case true:
                    for (i = 0; i < num.Length; i++)
                    {
                        res[i] = num[num.Length - 1 - i];
                    }
                    for (i = 0; i < res.Length; i++)
                    {
                        num[i] = res[i];
                    }
                    break;
                case false:
                    for (i = 0; i < num.Length; i++)
                    {
                        res[i] = num[i];
                    }
                    break;
            }
            return res;
        }
        /// <summary>
        /// 排序
        /// </summary>
        /// <param name="num">需要排序的数组</param>
        /// <param name="isBigToSmall">true:从大到小排序，false：以小到大排序</param>
        /// <returns></returns>
        public double[] BobCollate(double[] num, bool isBigToSmall = true)
        {
            double[] res = new double[num.Length];
            int i, j;
            for (i = 0; i < num.Length - 1; i++)
            {
                for (j = 0; j < num.Length - 1 - i; j++)
                {
                    if (num[j] > num[j + 1])
                    {
                        Swap(num, j, j + 1);
                    }
                }
            }
            switch (isBigToSmall)
            {
                case true:
                    for (i = 0; i < num.Length; i++)
                    {
                        res[i] = num[num.Length - 1 - i];
                    }
                    for (i = 0; i < res.Length; i++)
                    {
                        num[i] = res[i];
                    }
                    break;
                case false:
                    for (i = 0; i < num.Length; i++)
                    {
                        res[i] = num[i];
                    }
                    break;
            }
            return res;
        }
        /// <summary>
        /// 去除重复
        /// </summary>
        /// <param name="a">需要去重的数组</param>
        /// <returns></returns>
        public int[] RemoveSame(int[] a)
        {
            List<int> d = new List<int>(a);
            d.Sort();
            int time = d.Count - 1;
            while (time >= 1)
            {
                for (; d[time - 1].Equals(d[time]);)
                {
                    d.RemoveAt(time - 1);
                    time--;
                    if (time == 0)
                    {
                        break;
                    }
                }
                time--;
            }
            return d.ToArray();
        }
        /// <summary>
        /// 去除重复
        /// </summary>
        /// <param name="a">需要去重的数组</param>
        /// <returns></returns>
        public string[] RemoveSame(string[] a)
        {
            List<string> d = new List<string>(a);
            d.Sort();
            int time = d.Count - 1;
            while (time >= 1)
            {
                for (; d[time - 1].Equals(d[time]);)
                {
                    d.RemoveAt(time - 1);
                    time--;
                    if (time == 0)
                    {
                        break;
                    }
                }
                time--;
            }
            return d.ToArray();
        }
        /// <summary>
        /// 去除重复
        /// </summary>
        /// <param name="a">需要去重的数组</param>
        /// <returns></returns>
        public double[] RemoveSame(double[] a)
        {
            List<double> d = new List<double>(a);
            d.Sort();
            int time = d.Count - 1;
            while (time >= 1)
            {
                for (; d[time - 1].Equals(d[time]);)
                {
                    d.RemoveAt(time - 1);
                    time--;
                    if (time == 0)
                    {
                        break;
                    }
                }
                time--;
            }
            return d.ToArray();
        }
    }
}
